/**
 * @program: LeetCode
 * @description: LeetCode : 474. 一和零
 * @author: WXY
 * @create: 2023-01-10 20:29
 * @Version 1.0
 * <p>
 * str 中就是物品，每个物品就是 一个，
 * m 和 n 相当与是背包，一个二维的背包
 * 此题就是01背包，
 * dp[i][j] 最多有m个0，n个1的strs的最大子集的大小为dp[i][j]
 * dp[i][j] 可以由前一个数推导得到，dp[i - zeroNum][j - oneNum] + 1  ，如果当前str拿了，所以加1
 * dp[i][j] = Math.max(dp[i][j],dp[i - zeroNum][j-oneNum]+1);
 * <p>
 * 01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
 * 字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。
 **/
public class Num474_findMaxForm {
    //01背包一定是外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！
    public static int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String str : strs) {
            int zeroNum = 0, oneNum = 0;
            for (char ch : str.toCharArray()) {
                if (ch == '0') zeroNum++;
                else oneNum++;
            }
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
}
